package heap;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
 * 请注意，它是 排序后 的从小到达第 k 小元素，而不是第 k 个 不同 的元素。
 *
 *
 * 堆排序 ：  使用到条件 每行按元素升序排序 [](https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/shi-yong-dui-heapde-si-lu-xiang-jie-ling-fu-python/)
 * 二分查找： 使用到条件 每行和每列元素均按升序排序
 */
public class 有序矩阵中第K小的元素_378 {
    /**
     * 维护小根堆  最小值肯定是 matrix[0][0]
     * 用第一列的值初始化堆   然后每次弹出最小的一个 push最小的右边的那一个
     * 这样不是还是能保证候选人列表中每一个数字是每一行的最小值吗，那全局最小值必然在其中！
     * 弹出k - 1次之后  堆顶就是最小值
     *
     * 注意数组的用法  代替object对象值都是同类型的情况
     */
    public int kthSmallest(int[][] matrix, int k) {
        Queue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for(int i = 0; i< matrix.length; i++){
            heap.offer(new int[]{matrix[i][0], i, 0});
        }

        for(int i = 0; i < k - 1; i++ ) {
            int[] min = heap.poll();
            int x = min[1];
            int y = min[2];
            // 防止数组越界
            // 不用判断 = 的情况  每行弹完了  堆里个数就少一个
            //  但是其他行 肯定有数据在堆里
            //  只要其他行有数据  删了肯定就能放一个进来  堆肯定不会为空
            //  因为 1 <= k <= n^2  只有 k = n^2 的时候  会弹出到剩下 matrix[n-1][n-1] 在最后
            if(y != matrix.length - 1) {
                // 下一个候选人放进去
                heap.offer(new int[]{matrix[x][y + 1], x, y + 1});
            }
        }
        return heap.poll()[0];
    }


    /**
     * https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/you-xu-ju-zhen-zhong-di-kxiao-de-yuan-su-by-leetco/
     * 二维数组的二分查找  对值进行二分
     * 找分界线左上侧小于 值x的元素数量
     * 如果大于k  right = mid
     * 如果小于k  left = mid + 1
     */
    public int kthSmallest_binarySearch(int[][] matrix, int k) {
        int left = matrix[0][0];
        int right = matrix[matrix.length - 1][matrix.length - 1];
        // 二分最终到达left = right的时候就是目标值 k
        while (left < right) {
            int mid = (left + right) >> 1;
            // 小于mid值的元素个数小于k个 说明mid小于目标值  把left 改为mid + 1
            int cnt = ltMidCnt(matrix, mid);
            /* TODO 提前返回是有问题的  如果  有两个13   刚好mid = 14  小于14的有8个 实际应为13才是刚好有8个 因此还应再压缩 一直到边界相等
            if(cnt < k) {
                left = mid + 1;
            } else if(cnt > k) {
                right = mid;
            } else {
                return mid;
            }*/
           /* if(cnt <= k) {
                left = mid;
            } else if(cnt > k) {
                right = mid - 1;
            }*/
            // TODO 上面代码有问题
            // 二分一定是 left = mid +1 right = mid
            // 因为  如果 left = mid  将产生  mid = (left + right)/2 = (14 + 15) /2 = 14 = left 无限循环的情况
            // 因此一定要left + 1 对应小于  ？？？
            if(cnt < k) {
                left = mid + 1;
            } else if(cnt >= k) {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 从左下角开始找 小于往右 大于往上
     * 找小于mid值的元素个数
     * 也可从右上开始搜索
     * 可以双向搜索
     */
    private int ltMidCnt(int[][] matrix, int mid) {
        int x = matrix.length - 1;
        int y = 0;
        int cnt = 0;
        while ( x >= 0 && y < matrix.length ) {
            if(matrix[x][y] <= mid) {
                // 列中 满足条件的个数
                cnt += x + 1;
                y++;
            } else {
                x --;
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        有序矩阵中第K小的元素_378 a = new 有序矩阵中第K小的元素_378();
        a.kthSmallest_binarySearch(new int[][]{{1,5,9},{10,11,13},{12,13,15}}, 8);

    }
}
